home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus Leser 15 / Amiga Plus Leser CD 15.iso / Tools / Development / yacas_alg / yacas_morphos / share / yacas / examples / findsum.ys < prev    next >
Encoding:
Text File  |  2002-03-13  |  1.8 KB  |  54 lines
  1. /* O(2^n) algorithm for finding all combinations of numbers in a list
  2.  * that total a specific number.
  3.  *
  4.  * Calling sequence: FindSum(total_IsNumber, l_IsList)
  5.  *
  6.  * It returns a list of lists, each list containing a group of elements
  7.  * that add up to the requested number.
  8.  *
  9.  * This algorithm can be speeded up a lot if the summation is only done
  10.  * for numbers (by separating out the positive and negative values),
  11.  * but this routine is shorter and also works for any object you care
  12.  * to throw at it that has an addition operator defined for it (matrices,
  13.  * vectors, complex numbers, polynoms, etc.).
  14.  *
  15.  * It is a nice example of a piece of code that does things the Prolog
  16.  * way. The result is accumulated in one argument, which is treated as
  17.  * a list of results.
  18.  *
  19.  * Example:  
  20.  *
  21.  * In( 1 ) = FindSum(10,{2,3,4,5,6,7})
  22.  * Out( 1 ) = {{6,4},{7,3},{5,3,2}};
  23.  *
  24.  */
  25.  
  26. /* Main entry point for FindSum. */
  27. FindSum(_total, l_IsList) <--
  28.     [
  29.       Local(r);
  30.       r:={};                    /* r will contain the results. */
  31.       FindSum(total, l,{},0,r); /* find the solution */
  32.       r;                        /* return the results */
  33.     ];
  34.  
  35. /* this is an exact match: add the current sum to the results. */
  36. 10 # FindSum(_total, _l, _current, _total, _result) <-- DestructiveAppend(result, current);
  37.  
  38. /* All terms consumed. return results found. */
  39. 20 # FindSum(_total, {}, _current, _sum, _result)   <-- True;
  40.  
  41. /* Try to find sums, starting from current term and sum. */
  42. 30 # FindSum(_total, _l, _current, _sum, _result)   <--
  43.      [
  44.        Local(term);
  45.            /* New term that can be used for sum.   */
  46.        term:=Head(l);
  47.        /* try to find a sum WITHOUT this term. */
  48.        FindSum(total, Tail(l),      current, sum,      result);
  49.        /* try to find a sum WITH    this term. */
  50.        FindSum(total, Tail(l), term:current, sum+term, result);
  51.      ];
  52.  
  53.  
  54.